package com.str.BT;
import java.io.*;

public class BSTSaving {

// Inner class
  private static class BSTNode implements Serializable {
    Comparable data;
    BSTNode left;
    BSTNode right;

    BSTNode() {}
    BSTNode(Comparable obj) { data = obj; }
    BSTNode(Comparable obj, BSTNode leftChild, BSTNode rightChild) {
      data = obj; 
      left = leftChild; 
      right = rightChild;
    }

    public String toString()
    { return data.toString(); }
  }
  
  private BSTNode root;
  private int count;
    
  public void BSTSaving()
  {	clear(); }
  
  public final void clear() {
    root = null;
    count = 0;
  }

  public void insert(Comparable val) 
  { root = insert(root, val); }
  
  private BSTNode insert(BSTNode ref, Comparable val) {
  // Insert the element elem in this BST.
    if (ref == null) {
      count++;
      return new BSTNode(val);
    }
    else {
      int comp = val.compareTo(ref.data);
      if (comp < 0)
        ref.left = insert(ref.left, val);
      else  // comp >= 0
        ref.right = insert(ref.right, val);
      return ref;  	   	
    }
  }

  public String toString()  
  { return toString(root, 0); }
  
  private String toString(BSTNode ref, int level) {
  	String buf = "";
    if (ref != null) {
      buf += toString(ref.right, level+1);
      for (int i=0; i<level; i++)
        buf += "    ";
      buf += ref.data + "\n";
      buf += toString(ref.left, level+1);
    }
    return buf;
  }

  public void writeTree(String fileName, int i) throws IOException {   
    FileOutputStream outFile = new FileOutputStream(fileName);
    ObjectOutputStream outStream = new ObjectOutputStream(outFile);
    if (i == 1)
      writeTree1(root, outStream);
    else if (i == 2) {
      outStream.writeInt(count);
      writeTree2(root, outStream);
    }
    outStream.close();
  }
  
  private void writeTree1(BSTNode ref, ObjectOutputStream out) throws IOException {
    if (ref == null) return;
    out.writeObject(ref.data);
    writeTree1(ref.left, out);
    writeTree1(ref.right, out);
  }
  
  private void writeTree2(BSTNode ref, ObjectOutputStream out) throws IOException {
    if (ref == null) return;
    writeTree2(ref.left, out);    
    out.writeObject(ref.data);
    writeTree2(ref.right, out);
  }    
  
  public void readTree(String fileName, int i) 
      throws IOException, ClassNotFoundException {
    FileInputStream inFile = new FileInputStream(fileName);
    ObjectInputStream inStream = new ObjectInputStream(inFile); 
    clear();      	
  	if (i == 1)
  	  readTree1(inStream);
  	else if (i == 2) {
  	  int n = inStream.readInt();
  	  root = readTree2(inStream, n);
  	}
  	inStream.close();  
  }	   	  
  	  
  private void readTree1(ObjectInputStream in) 
      throws IOException, ClassNotFoundException {
  	try {	
      while (true) {
        Comparable val = (Comparable) in.readObject();
        insert(val);              
      }
    }
    catch (EOFException e) {}
  }  

  private BSTNode readTree2(ObjectInputStream in, int n)
      throws IOException, ClassNotFoundException {
  	if (n == 0) return null;
    BSTNode ref = new BSTNode();
    ref.left = readTree2(in, n/2);               
    Comparable val = (Comparable) in.readObject();       
    ref.data = val;
    ref.right = readTree2(in, (n-1)/2);    
    return ref;             
  }
  
  public static void main(String[] args) 
      throws IOException, ClassNotFoundException {
  	BSTSaving bst = new BSTSaving();
  	
    for (int i = 0; i < 10; i++) {
      int r = (int) (Math.random() * 26);	
      bst.insert(new Character((char) ('A' + r)));	
    }
    
    System.out.println("Original tree:");
    System.out.print(bst);
    
    // 1. Saving a binary search tree and then restoring it to its original shape
    System.out.println("Uses preorder traversal to save the tree to a file:");
    bst.writeTree("tree1.dat", 1);
    
    System.out.println("Restoring it to its original shape:");    
    bst.readTree("tree1.dat", 1); 
    System.out.print(bst);
    
    // 2. Saving a binary tree and then restoring it to a balanced shape    
    System.out.println("Uses inorder traversal to save the tree to a file:");
    bst.writeTree("tree2.dat", 2);
    
    System.out.println("Restoring it to a balanced shape:");    
    bst.readTree("tree2.dat", 2);
    System.out.print(bst);    
  }
}
